//
// Description: 6015. 统计可以被 K 整除的下标对数目
// Created by Loading on 2022/2/20.
//

#include <bits/stdc++.h>

using namespace std;

long long countPairs(vector<int> &nums, int k) {
    // 存储 k 的因子
    vector<int> divisors;

    // 寻找 k 的所有因子
    for (int i = 1; i * i <= k; ++i) {
        if (k % i == 0) {
            divisors.emplace_back(i);
            if (i * i < k) {// 防止在 i * i == k 时重复添加因子
                divisors.emplace_back(k / i);
            }
        }
    }

    long long ans = 0;
    // cnt[i] 表示因子 i 在当前位置的前面出现了多少次（每个数最多出现一次）
    unordered_map<int, int> cnt;
    for (int x : nums) {// 遍历数组，以当前位置作为固定数，从此位置向前寻找
        /* x 作为固定数，若想与另一个数的乘积是 k 的倍数，则另一个数必须是 k / gcd(x, k) 的倍数 */
        ans += cnt[k / gcd(x, k)];
        for (int d : divisors) {
            if (x % d == 0) {// k 的因子若在当前数的因子中出现，则增加次数
                ++cnt[d];
            }
        }
    }

    return ans;
}

int main() {
    vector<int> nums = {2, 3, 6};
    int k = 6;
    auto res = countPairs(nums, k);
    cout << res << endl;

    return 0;
}